A RAID system is an organization of data in an array of data storage devices, such as hard disk drives, to achieve varying levels of data availability and system performance. Data availability refers to the ability of the RAID system to provide data stored in the array of data storage devices even in the event of the failure of one or more of the individual data storage devices in the array. A measurement of system performance is the rate at which data can be sent to or received from the RAID system.
Of the five basic architectures developed for RAID systems, RAID 1 and RAID 5 architectures are most commonly used. A RAID 1 architecture involves an array having a first set of data storage devices with a second set of data storage devices which duplicates the data on the first set. In the event of the failure of a data storage device, the information is available from the duplicate device. The obvious drawback of this RAID system implementation is the necessity of doubling the storage space.
A RAID 5 architecture provides for redundancy of data by generating parity data. Each of the data storage devices are segmented into a plurality of units of data, known as blocks, containing equal numbers of data words. Blocks from each data storage device in the array covering the same data storage device address range form what are referred to as "stripes". A parity block is associated with each stripe. The parity block is generated by performing successive exclusive OR operations between corresponding data words in each of the data blocks. Changes to data blocks in a stripe necessitates re-computation of the parity block associated with the stripe. In a RAID 4 system, all parity blocks are stored on a single unit in the array. As a result, the data storage device containing the parity blocks is accessed disproportionately relative to the other data storage devices in the array. To eliminate the resulting constriction of data flow in a RAID 4 system, a RAID 5 architecture distributes the parity blocks across all of the data storage devices in the array. Typically in a RAID 5 system, a set of N+1 data storage devices forms the array. Each stripe has N blocks of data and one block of parity data. The block of parity data is stored in one of the N+1 data storage devices. The parity blocks corresponding to the remaining stripes of the RAID system are stored across the data storage devices in the array. For example, in a RAID 5 system using five data storage devices, the parity block for the first stripe of blocks may be written to the fifth device; the parity block for the second stripe of blocks may be written to the fourth drive; the parity block for the third stripe of blocks may be written to the third drive; etc. Typically, the location of the parity block in the array for succeeding blocks shifts to the succeeding logical device in the array, although other patterns may be used. More information detailing the architecture and performance of RAID systems can be found in the RAID Book: A Source Book for RAID Technology, by the RAID Advisory Board, 1993, the disclosure of which is incorporated herein by reference.
When data stored in the N+1 storage devices of the RAID 5 array is modified, the parity block for the stripe in which the data is located must also be modified. This modification process can occur through what is known as a "read-modify-write" sequence or a "write in place" sequence. In a read-modify-write sequence, the parity block is recomputed through a process of performing the exclusive OR operation between corresponding words of the data blocks forming the stripe.
A write in place sequence recomputes the parity block by removing the effect of the data currently contained in the storage locations which will be modified from the parity block and then adding the effect of the new data to the parity block. To perform a write in place sequence, the data presently stored in the data blocks having the storage locations which will be modified is read. The corresponding portion of the parity block of the stripe containing the storage locations which will be modified is read. The exclusive OR operation is performed between the data presently stored in the data blocks and the corresponding portion of the parity block to remove the effect of the presently stored data on the parity block. The exclusive OR operation is then performed between the new data and the result of the previous exclusive OR operation. This result is then stored on the data storage devices in the corresponding locations from which the portion of the parity block was loaded and the new data is stored in the stripe.
Efficiency considerations determine which one of these methods of parity block computation will be used. The factors used to determine which of these methods of parity block generation is most efficient vary with the configuration of the RAID system and the data blocks which are being modified. For example, if there are a large number of data storage devices which store portions of the stripe and changes have been made to data blocks which involve only a few of the data storage devices, the most efficient parity block re-computation method may be write in place. However, if a relatively large fraction of data storage devices are involved in the changes to the data blocks, the most efficient parity block re-computation method may be read-modify-write. The firmware controlling the operation of the RAID system determines the most efficient parity block re-computation method for each data transfer to the array.
Low cost RAID systems can be implemented by using software installed in the host computer system to perform the RAID system management functions. For this type of RAID system the host computer system manages the distribution of data blocks and parity blocks across an array of data storage devices and performs the parity block computation. As expected, this low cost RAID system implementation results in a significant reduction in the ability of the host computer system to perform its other data processing operations. High performance RAID systems use a dedicated controller to manage the data block and parity block storage in the array of data storage devices. For these high performance RAID systems, the host computer is able to interact with the RAID system as a single data storage unit.
Within the category of high performance RAID systems using controllers, there are low cost controllers and high performance controllers. Low cost controllers use the microprocessor on the controller to perform the parity block generation. This implementation of parity block generation makes a trade off in the performance of the RAID system controller to reduce the cost of the controller. High performance controllers utilize dedicated hardware, such as a state machine or a dedicated microprocessor, to more rapidly perform parity block generation.
The prior art dedicated hardware used in high performance controllers includes a single dedicated memory to store intermediate results used in the generation of the parity block. The process of storing a stripe of new data into the RAID system employing a read-modify-write sequence and using the parity generation logic of the dedicated hardware proceeds as follows:
1. As a data block of the stripe is transferred over the data bus of the RAID system to the data storage devices, the dedicated hardware in the RAID controller writes the data block into the single dedicated memory. PA1 2. As data words of the next data block of the stripe are transferred over the data bus of the RAID system to the data storage devices, they are loaded into the dedicated hardware in the RAID controller. PA1 3. As the data words of the previous step are loaded into the dedicated hardware, the corresponding data words or results of previous exclusive OR operations stored in the single dedicated memory are also loaded into the dedicated hardware. PA1 4. An exclusive OR operation is performed using the corresponding data words as operands. PA1 5. The result of the exclusive OR operation is written back into the single dedicated memory. PA1 6. These steps, beginning with step 2, are repeated until all of the corresponding words of the data blocks of the stripe have undergone the exclusive OR operation. PA1 7. The resulting newly generated parity block for the stripe is stored in the data storage devices in the array designated to hold the parity block for that stripe.
This read-modify-write method of parity block generation requires loading the intermediate results stored in the single dedicated memory into the dedicated hardware and then storing the results of the exclusive OR operation in the single dedicated memory for each exclusive OR operation performed. Computation of the parity block is done as the data stripe is transferred over the bus. Computation of the parity block using the prior art parity generation logic requires two accesses to the single dedicated memory for each data word transferred over the bus.
For RAID systems which transfer data over the data bus up to 40 MB/s, this method of parity data block generation can be performed at a rate sufficient to meet the data transfer rates of the bus. For the next generation RAID systems having data transfer rates of greater than 100 MB/s over the bus, this method of parity block generation cannot be performed sufficiently fast to allow parity block generation to occur as data stripes are transferred over the bus. Use of this method of parity block generation in the next generation of RAID systems would require a reduction in the data transfer rates of the bus. A system for generating parity blocks which will not reduce the data transfer rate performance of the bus is required to achieve optimum performance in the next generation of RAID systems.